package com.jp.algorithm.graph;

import java.util.*;

public class AdjacencyMatrixGraph {
    int[][] matrix = null;
    int size;

    public AdjacencyMatrixGraph(int size) {
        this.size = size;
        matrix = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                matrix[i][j] = 0;
            }
        }
    }


    public void addEdge(int start, int end, int weight) {
        if (matrix[start][end] == 0) {
            matrix[start][end] = weight;
        }
    }


    public void dfs() {
        int[] visited = new int[size];
        for(int i=0;i<size;i++){
            if(visited[i]==0){
                dfsInner(i,visited);
            }
        }
    }

    public void dfsInner(int i, int[] visited) {
        if (visited[i] == 0) {
            System.out.println(i);
            visited[i] = 1;
        }
        for (int j = 0; j < size; j++) {
            if (matrix[i][j] != 0) {
                dfsInner(j, visited);
            }
        }
    }


    public Boolean isBinaryInner(int i,int col, int[] colorArray){
        colorArray[i]=col;
        for (int j = 0; j < size; j++) {
            if (matrix[i][j] != 0) {
                if(colorArray[j] == col)
                    return false;
                int newCol = col==0 ? 1 : 0;
                if(colorArray[j]==-1 && !isBinaryInner(j, newCol,colorArray)){
                    return false;
                }
            }
        }
        return true;
    }
    public  Boolean isBinary() {
        int[] color = new int[size];

        for(int i=0;i<size;i++){
            color[i]=-1;
        }
        return isBinaryInner(0,0,color);
    }

    public static void testDsf() {
        AdjacencyMatrixGraph adjacencyMatrixGraph = new AdjacencyMatrixGraph(5);
        adjacencyMatrixGraph.addEdge(0, 2, 1);
        adjacencyMatrixGraph.addEdge(2, 3, 1);
        adjacencyMatrixGraph.addEdge(0, 3, 1);
        adjacencyMatrixGraph.addEdge(3, 4, 1);
        adjacencyMatrixGraph.addEdge(1, 4, 1);
        adjacencyMatrixGraph.addEdge(1, 0, 1);
        adjacencyMatrixGraph.dfs();
    }
    public static void testBinaryGraph() {
        AdjacencyMatrixGraph adjacencyMatrixGraph = new AdjacencyMatrixGraph(5);

        adjacencyMatrixGraph.addEdge(0, 2, 1);
        adjacencyMatrixGraph.addEdge(2, 0, 1);
        adjacencyMatrixGraph.addEdge(0, 3, 1);
        adjacencyMatrixGraph.addEdge(3, 0, 1);
        adjacencyMatrixGraph.addEdge(2, 1, 1);
        adjacencyMatrixGraph.addEdge(1, 2, 1);
        adjacencyMatrixGraph.addEdge(3, 4, 1);
        adjacencyMatrixGraph.addEdge(4, 3, 1);
        adjacencyMatrixGraph.addEdge(1, 4, 1);
        adjacencyMatrixGraph.addEdge(4, 1, 1);
        System.out.println(adjacencyMatrixGraph.isBinary());
    }



    public static void main(String[] args) {
        testBinaryGraph();
    }
}
